package hot100.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @
 * @date 2025/08/23
 */
public class 三数之和_15 {

    public static void main(String[] args) {

    }

    /**
     * 排序+双指针
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int targetNum = -1 * nums[i];
            // 注意，枚举第一个数的时候，如果有重复元素，要选第一个出现的元素，因为可能成为第二和第三个元素
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1, right = nums.length - 1;

            while (left < right) {
                if (nums[left] + nums[right] == targetNum) {
                    List<Integer> list = Arrays.asList(nums[i], nums[left], nums[right]);
                    lists.add(list);

                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (right > left && nums[right] == nums[right - 1]) {
                        right--;
                    }
                }
                if (nums[left] + nums[right] > targetNum) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return lists;
    }

}
